import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

public class GameState implements Comparable<GameState> {
	HashSet<Point> boxes;
	GameState parent;
	Point playerPos;
	Point playerBeforePush = null;
	char lastMove;
	HashSet<Point> playerArea;
	double heuristic = 0.0;
	double cost;

	public GameState(ArrayList<Point> boxes, GameState parent, Point playerPos,double cost) {
		this.boxes = new HashSet<Point>();
		// Deep copy
		this.boxes.addAll(boxes);
		this.parent = parent;
		this.playerPos = playerPos;
		playerArea = new HashSet<Point>(10); // TODO adjust the capacity
		findArea(playerPos);
		this.cost = cost;
		calcHeuris();
	}

	/**
	 * For a point, find empty adjacent spaces
	 * 
	 * @param p
	 *            point
	 * @return Point[][]
	 */
	public ArrayList<Point> findFreeNeighbours(Point p) {
		char[][] tempMap = generateMap();
		ArrayList<Point> result = new ArrayList<Point>();
		// check the 4 neighbours
		if (tempMap.length > (p.x + 1)
				&& (tempMap[p.x + 1][p.y] == ' ' || tempMap[p.x + 1][p.y] == '.')) {
			result.add(new Point(p.x + 1, p.y));
		}
		if (p.x - 1 >= 0
				&& (tempMap[p.x - 1][p.y] == ' ' || tempMap[p.x - 1][p.y] == '.')) {
			result.add(new Point(p.x - 1, p.y));
		}
		if (tempMap[p.x].length > p.y + 1
				&& (tempMap[p.x][p.y + 1] == ' ' || tempMap[p.x][p.y + 1] == '.')) {
			result.add(new Point(p.x, p.y + 1));
		}
		if (p.y - 1 >= 0
				&& (tempMap[p.x][p.y - 1] == ' ' || tempMap[p.x][p.y - 1] == '.')) {
			result.add(new Point(p.x, p.y - 1));
		}

		return result;
	}

	/**
	 * Change the playerArea attribute according to the possible area move. Use
	 * BFS
	 * 
	 * @param playerPosition
	 */
	public void findArea(Point playerPosition) {
		// Iterative BFS
		Stack<Point> stack = new Stack<Point>();
		stack.push(playerPosition);
		playerArea.add(playerPosition);
		while (!stack.isEmpty()) {
			Point p = stack.pop();
			for (Point neighbors : findFreeNeighbours(p)) {
				if (playerArea.add(neighbors)) {
					stack.push(neighbors);
				}
			}
		}

	}

	/**
	 * Return the children of the GameState I.e all the possible moves but not
	 * the move already done.
	 */
	public ArrayList<GameState> findChildren() {

		ArrayList<GameState> childs = new ArrayList<GameState>();
		for (Point box : boxes) {

			ArrayList<Point> new_boxes = new ArrayList<Point>(boxes);

			Point new_player_pos = new Point(box);
			new_boxes.remove(box);

			String next_move = possibleMovesBox(box);
			for (int i = 0; i < next_move.length(); ++i) {
				Point playPosBeforePush = new Point();
				Point new_box = null;
				new_box = moveBox(box, next_move.charAt(i), playPosBeforePush);
				new_boxes.add(new_box);

				GameState child = new GameState(new_boxes, this, new_player_pos,cost+heuristic);

				child.playerBeforePush = playPosBeforePush;
				child.findLastMove();

				childs.add(child);

				new_boxes.remove(new_box);
			}

		}
		// Identify possible moves
		return childs;
	}

	private Point moveBox(Point box_pos, char direction, Point beforePush) {

		Point new_box_pos = (Point) box_pos.clone();

		switch (direction) {
		case 'U':
			new_box_pos = new Point(new_box_pos.x - 1, new_box_pos.y);
			beforePush.x = new_box_pos.x + 2;
			beforePush.y = new_box_pos.y;
			break;
		case 'D':
			new_box_pos = new Point(new_box_pos.x + 1, new_box_pos.y);
			beforePush.x = new_box_pos.x - 2;
			beforePush.y = new_box_pos.y;
			break;
		case 'L':
			new_box_pos = new Point(new_box_pos.x, new_box_pos.y - 1);
			beforePush.x = new_box_pos.x;
			beforePush.y = new_box_pos.y + 2;
			break;
		case 'R':
			new_box_pos = new Point(new_box_pos.x, new_box_pos.y + 1);
			beforePush.x = new_box_pos.x;
			beforePush.y = new_box_pos.y - 2;
			break;
		default:
			return new_box_pos;
		}

		return new_box_pos;
	}

	/**
	 * Check if the current state contains all the boxes on their goals.
	 * 
	 * @return boolean
	 */
	public boolean isGoalState() {
		return Main.goals.equals(boxes);

		// for (Point boxe : boxes) {
		// if (!Main.goals.contains(boxe)) {
		// return false;
		// }
		// }
		// return true;
	}

	/**
	 * Find if the GameState is a deadlock using patterns.
	 * 
	 * @return
	 */
	public boolean isDeadlock() {

		for (Pattern patt : Main.patterns) {
			if (patt.isPatternDeadlock(boxes)) {
				return true;
			}
		}

		return false;

		// for (Point box : boxes) {
		//
		// // $$
		// // $$
		//
		// if (boxes.contains(new Point(box.x + 1, box.y))
		// && boxes.contains(new Point(box.x + 1, box.y + 1))
		// && boxes.contains(new Point(box.x, box.y + 1))) {
		// return true;
		// }
		//
		// // $$
		// // #$
		// if (Main.map[box.x + 1][box.y] == '#'
		// && boxes.contains(new Point(box.x + 1, box.y + 1))
		// && boxes.contains(new Point(box.x, box.y + 1))) {
		// return true;
		// }
		//
		// // #$
		// // $$
		// if (Main.map[box.x + 1][box.y] == '#'
		// && boxes.contains(new Point(box.x + 1, box.y + 1))
		// && boxes.contains(new Point(box.x, box.y + 1))) {
		// return true;
		// }
		//
		// // $$
		// // $#
		// if (Main.map[box.x + 1][box.y + 1] == '#'
		// && boxes.contains(new Point(box.x + 1, box.y))
		// && boxes.contains(new Point(box.x, box.y + 1))) {
		// return true;
		// }
		//
		// // $#
		// // $$
		// if (Main.map[box.x][box.y + 1] == '#'
		// && boxes.contains(new Point(box.x + 1, box.y + 1))
		// && boxes.contains(new Point(box.x + 1, box.y))) {
		// return true;
		// }
		//
		// // #$
		// // #$
		// if (Main.map[box.x][box.y - 1] == '#'
		// && Main.map[box.x + 1][box.y - 1] == '#'
		// && boxes.contains(new Point(box.x + 1, box.y))) {
		// return true;
		// }
		// // $#
		// // $#
		// if (Main.map[box.x][box.y + 1] == '#'
		// && Main.map[box.x + 1][box.y + 1] == '#'
		// && boxes.contains(new Point(box.x + 1, box.y))) {
		// return true;
		// }
		//
		// // ##
		// // $$
		// if (Main.map[box.x - 1][box.y] == '#'
		// && Main.map[box.x - 1][box.y + 1] == '#'
		// && boxes.contains(new Point(box.x, box.y + 1))) {
		// return true;
		// }
		//
		// // $$
		// // ##
		// if (Main.map[box.x + 1][box.y] == '#'
		// && Main.map[box.x + 1][box.y + 1] == '#'
		// && boxes.contains(new Point(box.x, box.y + 1))) {
		// return true;
		// }
		//
		// }
		//
		// return false;
	}

	/**
	 * Create the map with the boxes and the goals
	 * 
	 * @return
	 */
	public char[][] generateMap() {
		char[][] result = new char[Main.map.length][Main.map[0].length];
		for (int i = 0; i < result.length; i++) {
			// result = new char[i][Main.map[i].length];
			for (int j = 0; j < Main.map[i].length; j++) {
				result[i][j] = Main.map[i][j];
			}
		}
		for (Point pt : boxes) {
			if (result[pt.x][pt.y] == '.') {
				result[pt.x][pt.y] = '*';
			} else {
				result[pt.x][pt.y] = '$';
			}
		}// end adding the boxes

		// add the player to the map

		// if (result[playerPos.x][playerPos.y] == '.') {
		// result[playerPos.x][playerPos.y] = '+';
		// } else {
		// result[playerPos.x][playerPos.y] = '@';
		// }
		return result;
	}

	/**
	 * Get all the movable boxes and the possible moves.
	 * 
	 * @return
	 */
	private HashMap<Point, String> getMovableBoxes() {
		HashMap<Point, String> movableBoxes = new HashMap<Point, String>();

		for (Point box : boxes) {
			String moves = possibleMovesBox(box);
			if (!moves.equals("")) {
				movableBoxes.put(box, moves);
			}
		}

		// Maybe we should return the first box that is movable.
		return movableBoxes;
	}

	/**
	 * Check if the box is movable, i.e. the player can reach it and can move it
	 * Up, Down, Left, Right
	 * 
	 * @param boxe
	 * @return in which position it can move Parse the String to an array or
	 *         delete the last character to get the next possible move.
	 */
	public String possibleMovesBox(Point box) {
		// TODO need to check the bound...
		String possibleMove = "";
		// Check if the box is in the player Area.

		// move up
		if (playerArea.contains(new Point(box.x + 1, box.y))
				&& Main.map[box.x - 1][box.y] != '#'
				&& !boxes.contains(new Point(box.x - 1, box.y))
				&& !Main.deadLock_positions
						.contains(new Point(box.x - 1, box.y))) {
			possibleMove += "U";
		}
		// Down
		if (playerArea.contains(new Point(box.x - 1, box.y))
				&& Main.map[box.x + 1][box.y] != '#'
				&& !boxes.contains(new Point(box.x + 1, box.y))
				&& !Main.deadLock_positions
						.contains(new Point(box.x + 1, box.y))) {
			possibleMove += "D";
		}
		// Right
		if (playerArea.contains(new Point(box.x, box.y - 1))
				&& Main.map[box.x][box.y + 1] != '#'
				&& !boxes.contains(new Point(box.x, box.y + 1))
				&& !Main.deadLock_positions
						.contains(new Point(box.x, box.y + 1))) {

			possibleMove += "R";
		}
		// Left
		if (playerArea.contains(new Point(box.x, box.y + 1))
				&& Main.map[box.x][box.y - 1] != '#'
				&& !boxes.contains(new Point(box.x, box.y - 1))
				&& !Main.deadLock_positions
						.contains(new Point(box.x, box.y - 1))) {

			possibleMove += "L";
		}

		return possibleMove;
	}

	/**
	 * generate the path taken by player from its previous location to its
	 * current one
	 * 
	 * @return the partial path
	 */
	public String getPartialPath() {
		if (parent != null) {
			return Node.findPath(parent, this);
		} else {
			return "";
		}
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((boxes == null) ? 0 : boxes.hashCode());
		result = prime * result
				+ ((playerArea == null) ? 0 : playerArea.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		GameState other = (GameState) obj;
		if (boxes == null) {
			if (other.boxes != null)
				return false;
		} else if (!boxes.equals(other.boxes))
			return false;
		if (playerArea == null) {
			if (other.playerArea != null)
				return false;
		} else if (!playerArea.equals(other.playerArea))
			return false;
		return true;
	}

	public void print() {
		char[][] map = generateMap();
		// for (Point p : playerArea) {
		// map[p.x][p.y] = 'A';
		// }

		map[playerPos.x][playerPos.y] = 'P';

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println("");
		}

	}

	public void findLastMove() {
		if (playerBeforePush.x == playerPos.x - 1) {
			lastMove = 'D';
		}
		if (playerBeforePush.x == playerPos.x + 1) {
			lastMove = 'U';
		}
		if (playerBeforePush.y == playerPos.y - 1) {
			lastMove = 'R';
		}
		if (playerBeforePush.y == playerPos.y + 1) {
			lastMove = 'L';
		}
	}

	public void calcHeuris() {
		for (Point box : boxes) {
			double minDist = Integer.MAX_VALUE;
			for (Point goal : Main.goals) {
				if (!boxes.contains(goal)) {
					minDist = Math.min(minDist, goal.distance(box));
				}
			}
			heuristic += minDist;
		}
		heuristic += cost;
	}

	@Override
	public int compareTo(GameState o) {
		if (heuristic < o.heuristic) {
			return 1;
		} else if (heuristic > o.heuristic) {
			return -1;
		} else {
			return 0;
		}
	}
}